Dijkstra's Algorithm
    Named after its E.W. Dijkstra, who proposed it, Dijkstra’s algorithm finds the shortest paths in a Graph G = ( V, E ) from a source node to all other nodes in the graph. Since it is a recursive algorithm on V, its correctness can be proved by induction. Here is the naďve O( n^2 ) algorithm that I implemented:

      Dijkstra's algorithm can be expressed as follows:

      • G - arbitrary connected graph
      • v0 - is the start vertex
      • V - is the set of all vertices in G
      • S - set of all vertices with p
      • d - array of best estimates of shortest path to each vertex
      • pi - array of predecessors for each vertex

      The basic procedure is as follows:

      1. Initialize d and pi,
      2. Set S to empty,
      3. While V-S not empty,
        1. Sort vertices in V-S according to best estimates of distance to source
        2. Add u, the closest vertex in V-S, to S
        3. Relax all the vertices still in V-S connected to u.

      The Relax procedure is as follows:

        For two connected nodes u and v, if the estimate of the distance from the source to the current node u is greater than the distance if the path proceeds through v, then make v the predecessor of u and update the distance estimate.

    Dijstra’s Algorithm can be optimized by using a heap to hold the vertices remaining to be processed. Doing so means the ExtractMin() operation will take O( log n ) time instead of O( n ) time. Hence, Dijkstra's algorithm can be made to run in O( n log n ) time.

HOME | PREV | NEXT